#include <iostream>
#include <string>
using namespace std;


/**
  * @方法: 两个字符串的删除操作 的进阶问题
  * @时间复杂度: o()
  * @空间复杂度: o()
  * @评价:
*/
int deleteAll(string s){
    int ans = 0;
    for(int i=0;i<s.length();i++) ans += s[i];
    return ans;
}

int minimumDeleteSum(string s1, string s2) {
    int dp[503][503];
    for(int i=0;i<=s1.length();i++) dp[i][0] = deleteAll(s1.substr(0,i));
    for(int j=0;j<=s2.length();j++) dp[0][j] = deleteAll(s2.substr(0,j));

    for(int i=1;i<=s1.length();i++){
        for(int j=1;j<=s2.length();j++){
            if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
        }
    }
    return dp[s1.length()][s2.length()];
}


